SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Selection algorithm</title>

</head>

Selection algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For simulated natural selection in genetic algorithms, see <a href="Selection_(genetic_algorithm)" class="mw-redirect" title="Selection (genetic algorithm)">Selection (genetic algorithm)</a>.</div>

In <a href="Computer_science" title="Computer science">computer science</a>, a selection algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> for finding the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th <a href="Order_statistic" title="Order statistic">order statistic</a>. Selection includes as special cases the problems of finding the <a href="Minimum" class="mw-redirect" title="Minimum">minimum</a>, <a href="Median" title="Median">median</a>, and <a href="Maximum" class="mw-redirect" title="Maximum">maximum</a> element in the collection. Selection algorithms include <a href="Quickselect" title="Quickselect">quickselect</a>, and the <a href="Median_of_medians" title="Median of medians">median of medians</a> algorithm. When applied to a collection of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> values, these algorithms take <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> as expressed using <a href="Big_O_notation" title="Big O notation">big O notation</a>. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted <a href="Array_(data_structure)" title="Array (data structure)">array</a> takes time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Problem_statement">Problem statement</h2></div>

An algorithm for the selection problem takes as input a collection of values, and a number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. It outputs the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest of these values, or, in some versions of the problem, a collection of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> smallest values. For this to be well-defined, it should be possible to <a href="Sorting" title="Sorting">sort</a> the values into an order from smallest to largest; for instance, they may be <a href="Integer_(computer_science)" title="Integer (computer science)">integers</a>, <a href="Floating-point_number" class="mw-redirect" title="Floating-point number">floating-point numbers</a>, or some other kind of <a href="Object_(computer_science)" title="Object (computer science)">object</a> with a numeric key. However, they are not assumed to have been already sorted. Often, selection algorithms are restricted to a comparison-based <a href="Model_of_computation" title="Model of computation">model of computation</a>, as in <a href="Comparison_sort" title="Comparison sort">comparison sort</a> algorithms, where the algorithm has access to a <a href="Relational_operator" title="Relational operator">comparison operation</a> that can determine the relative ordering of any two values, but may not perform any other kind of <a href="Arithmetic" title="Arithmetic">arithmetic operations</a> on these values.<a href="#cite_note-cunmun-1">[1]</a>

To simplify the problem, some works on this problem assume that the values are all distinct from each other,<a href="#cite_note-clrs-2">[2]</a> or that some consistent tie-breaking method has been used to assign an ordering to pairs of items with the same value as each other. Another variation in the problem definition concerns the numbering of the ordered values: is the smallest value obtained by setting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=0}</annotation>

</semantics>

</math><img src="./6307c8a99dad7d0bcb712352ae0a748bd99a038b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=0}" loading="lazy">, as in <a href="Zero-based_numbering" title="Zero-based numbering">zero-based numbering</a> of arrays, or is it obtained by setting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=1}</annotation>

</semantics>

</math><img src="./6c035ffa69b5bca8bf2d16c3da3aaad79a8bcbfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=1}" loading="lazy">, following the usual English-language conventions for the smallest, second-smallest, etc.? This article follows the conventions used by Cormen et al., according to which all values are distinct and the minimum value is obtained from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=1}</annotation>

</semantics>

</math><img src="./6c035ffa69b5bca8bf2d16c3da3aaad79a8bcbfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=1}" loading="lazy">.<a href="#cite_note-clrs-2">[2]</a>

With these conventions, the maximum value, among a collection of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> values, is obtained by setting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=n}</annotation>

</semantics>

</math><img src="./c4b8cc6fcba0c0b24656b0fb33414d2e6cffb83c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.704ex; height:2.176ex;" alt="{\displaystyle k=n}" loading="lazy">. When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is an <a href="Odd_number" class="mw-redirect" title="Odd number">odd number</a>, the <a href="Median" title="Median">median</a> of the collection is obtained by setting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=(n+1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=(n+1)/2}</annotation>

</semantics>

</math><img src="./9c7cd8f54d5722c11ebfbfed1070d40df6feab8c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.841ex; height:2.843ex;" alt="{\displaystyle k=(n+1)/2}" loading="lazy">. When <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is even, there are two choices for the median, obtained by rounding this choice of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> down or up, respectively: the lower median with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=n/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=n/2}</annotation>

</semantics>

</math><img src="./e121b1ddb69638f4126c92f975fbf1c36d78087c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.029ex; height:2.843ex;" alt="{\displaystyle k=n/2}" loading="lazy"> and the upper median with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=n/2+1}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=n/2+1}</annotation>

</semantics>

</math><img src="./4bcd95ba3189ae2425a89fa84b9dd8f10012a68d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.032ex; height:2.843ex;" alt="{\displaystyle k=n/2+1}" loading="lazy">.<a href="#cite_note-clrs-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Sorting_and_heapselect">Sorting and heapselect</h3></div>

As a baseline algorithm, selection of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value in a collection of values can be performed by the following two steps:

<ul><li><a href="Sorting" title="Sorting">Sort</a> the collection</li>

<li>If the output of the sorting algorithm is an <a href="Array_(data_type)" title="Array (data type)">array</a>, retrieve its <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element; otherwise, scan the sorted sequence to find the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element.</li></ul>

The time for this method is dominated by the sorting step, which requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\log n)}</annotation>

</semantics>

</math><img src="./1b8781cea4259c3bd43204e02d08b9b9ce8fe0ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.153ex; height:2.843ex;" alt="{\displaystyle \Theta (n\log n)}" loading="lazy"> time using a <a href="Comparison_sort" title="Comparison sort">comparison sort</a>.<a href="#cite_note-clrs-2">[2]</a><a href="#cite_note-skiena-3">[3]</a> Even when <a href="Integer_sorting" title="Integer sorting">integer sorting</a> algorithms may be used, these are generally slower than the linear time that may be achieved using specialized selection algorithms. Nevertheless, the simplicity of this approach makes it attractive, especially when a highly-optimized sorting routine is provided as part of a runtime library, but a selection algorithm is not. For inputs of moderate size, sorting can be faster than non-random selection algorithms, because of the smaller constant factors in its running time.<a href="#cite_note-erickson-4">[4]</a> This method also produces a sorted version of the collection, which may be useful for other later computations, and in particular for selection with other choices of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">.<a href="#cite_note-skiena-3">[3]</a>

For a sorting algorithm that generates one item at a time, such as <a href="Selection_sort" title="Selection sort">selection sort</a>, the scan can be done in tandem with the sort, and the sort can be terminated once the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element has been found. One possible design of a consolation bracket in a <a href="Single-elimination_tournament" title="Single-elimination tournament">single-elimination tournament</a>, in which the teams who lost to the eventual winner play another mini-tournament to determine second place, can be seen as an instance of this method.<a href="#cite_note-bfprt-5">[5]</a> Applying this optimization to <a href="Heapsort" title="Heapsort">heapsort</a> produces the <a href="Heapselect" class="mw-redirect" title="Heapselect">heapselect</a> algorithm, which can select the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n+k\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n+k\log n)}</annotation>

</semantics>

</math><img src="./9e04c4c417d3014ce4329a545cf62aa6943762ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.17ex; height:2.843ex;" alt="{\displaystyle O(n+k\log n)}" loading="lazy">.<a href="#cite_note-brodal-6">[6]</a> This is fast when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is small relative to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, but degenerates to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> for larger values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, such as the choice <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=n/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=n/2}</annotation>

</semantics>

</math><img src="./e121b1ddb69638f4126c92f975fbf1c36d78087c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.029ex; height:2.843ex;" alt="{\displaystyle k=n/2}" loading="lazy"> used for median finding.

<div class="mw-heading mw-heading3"><h3 id="Pivoting">Pivoting</h3></div>

Many methods for selection are based on choosing a special "pivot" element from the input, and using comparisons with this element to divide the remaining <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> input values into two subsets: the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> of elements less than the pivot, and the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> of elements greater than the pivot. The algorithm can then determine where the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value is to be found, based on a comparison of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> with the sizes of these sets. In particular, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\leq |L|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\leq |L|}</annotation>

</semantics>

</math><img src="./819b5d43513143c19e678002607e6261c3f8fd70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.186ex; height:2.843ex;" alt="{\displaystyle k\leq |L|}" loading="lazy">, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy">, and can be found recursively by applying the same selection algorithm to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=|L|+1}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=|L|+1}</annotation>

</semantics>

</math><img src="./e4a5df55080d6953ac94efb157df80d5b2a6a85c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.189ex; height:2.843ex;" alt="{\displaystyle k=|L|+1}" loading="lazy">, then the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value is the pivot, and it can be returned immediately. In the remaining case, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy">, and more specifically it is the element in position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-|L|-1}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-|L|-1}</annotation>

</semantics>

</math><img src="./55eeb2c89adc8f3b5f4d9f5ac0221aa52c09c9df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.931ex; height:2.843ex;" alt="{\displaystyle k-|L|-1}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy">. It can be found by applying a selection algorithm recursively, seeking the value in this position in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy">.<a href="#cite_note-kletar-7">[7]</a>

As with the related pivoting-based <a href="Quicksort" title="Quicksort">quicksort</a> algorithm, the partition of the input into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> may be done by making new collections for these sets, or by a method that partitions a given list or array data type in-place. Details vary depending on how the input collection is represented.<a href="#cite_note-8">[8]</a> The time to compare the pivot against all the other values is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">.<a href="#cite_note-kletar-7">[7]</a> However, pivoting methods differ in how they choose the pivot, which affects how big the subproblems in each recursive call will be. The efficiency of these methods depends greatly on the choice of the pivot. If the pivot is chosen badly, the running time of this method can be as slow as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>

</semantics>

</math><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy">.<a href="#cite_note-erickson-4">[4]</a>

<ul><li>If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a <a href="Geometric_series" title="Geometric series">geometric series</a> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">. However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each call.<a href="#cite_note-kletar-7">[7]</a></li>

<li><a href="Quickselect" title="Quickselect">Quickselect</a> chooses the pivot uniformly at random from the input values. It can be described as a <a href="Prune_and_search" title="Prune and search">prune and search</a> algorithm,<a href="#cite_note-gootam-9">[9]</a> a variant of <a href="Quicksort" title="Quicksort">quicksort</a>, with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy">, quickselect only makes one of these two calls. Its <a href="Expected_time" class="mw-redirect" title="Expected time">expected time</a> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">.<a href="#cite_note-clrs-2">[2]</a><a href="#cite_note-kletar-7">[7]</a><a href="#cite_note-gootam-9">[9]</a> For any constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, the probability that its number of comparisons exceeds <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Cn}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Cn}</annotation>

</semantics>

</math><img src="./7eb08676206844b06ee1ddd827013317bd52e950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.161ex; height:2.176ex;" alt="{\displaystyle Cn}" loading="lazy"> is superexponentially small in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">.<a href="#cite_note-devroye-10">[10]</a></li>

<li>The <a href="Floyd%E2%80%93Rivest_algorithm" title="Floyd–Rivest algorithm">Floyd–Rivest algorithm</a>, a variation of quickselect, chooses a pivot by randomly sampling a subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> data values, for some sample size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">, and then recursively selecting two elements somewhat above and below position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle rk/n}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle rk/n}</annotation>

</semantics>

</math><img src="./d2835384f8d2a01405d6d05878d0b21d2cb7829a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.817ex; height:2.843ex;" alt="{\displaystyle rk/n}" loading="lazy"> of the sample to use as pivots. With this choice, it is likely that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+\min(k,n-k)+o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+\min(k,n-k)+o(n)}</annotation>

</semantics>

</math><img src="./0d0b8ee1d688913b4218c474b61d4bda3f8a5c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.783ex; height:2.843ex;" alt="{\displaystyle n+\min(k,n-k)+o(n)}" loading="lazy">.<a href="#cite_note-floriv-11">[11]</a> In their original work, Floyd and Rivest claimed that the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(n)}</annotation>

</semantics>

</math><img src="./afdac2125205278017cf549e9b004f8f6fd829c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.332ex; height:2.843ex;" alt="{\displaystyle o(n)}" loading="lazy"> term could be made as small as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {n}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {n}})}</annotation>

</semantics>

</math><img src="./f5526ab1252c0f682bbe07c0ad67c0f29de5522b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.913ex; height:3.009ex;" alt="{\displaystyle O({\sqrt {n}})}" loading="lazy"> by a recursive sampling scheme, but the correctness of their analysis has been questioned.<a href="#cite_note-brown-12">[12]</a><a href="#cite_note-prt-13">[13]</a> Instead, more rigorous analysis has shown that a version of their algorithm achieves <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {n\log n}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {n\log n}})}</annotation>

</semantics>

</math><img src="./94d15b4cf04b620d88c42bf9610e8b80aa0f07a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.442ex; height:3.509ex;" alt="{\displaystyle O({\sqrt {n\log n}})}" loading="lazy"> for this term.<a href="#cite_note-knuth-14">[14]</a> Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a <a href="True_random_number_generator" class="mw-redirect" title="True random number generator">true random number generator</a>, a version of the Floyd–Rivest algorithm using a <a href="Pseudorandom_number_generator" title="Pseudorandom number generator">pseudorandom number generator</a> seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.<a href="#cite_note-karrag-15">[15]</a></li></ul>

<ul><li>The <a href="Median_of_medians" title="Median of medians">median of medians</a> method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n/5}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n/5}</annotation>

</semantics>

</math><img src="./847a5db9507e91d2db71ca655c26ba2395ad7992.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.72ex; height:2.843ex;" alt="{\displaystyle n/5}" loading="lazy"> medians. Using the resulting median of medians as the pivot produces a partition with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max(|L|,|R|)\leq 7n/10}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max(|L|,|R|)\leq 7n/10}</annotation>

</semantics>

</math><img src="./89c196a23e40969ce1c03dd723649087c680b840.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.246ex; height:2.843ex;" alt="{\displaystyle \max(|L|,|R|)\leq 7n/10}" loading="lazy">. Thus, a problem on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements is reduced to two recursive problems on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n/5}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n/5}</annotation>

</semantics>

</math><img src="./847a5db9507e91d2db71ca655c26ba2395ad7992.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.72ex; height:2.843ex;" alt="{\displaystyle n/5}" loading="lazy"> elements (to find the pivot) and at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 7n/10}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 7n/10}</annotation>

</semantics>

</math><img src="./066ca5ce08676476e5cac70d99101ce42a8058de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.045ex; height:2.843ex;" alt="{\displaystyle 7n/10}" loading="lazy"> elements (after the pivot is used). The total size of these two recursive subproblems is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 9n/10}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 9n/10}</annotation>

</semantics>

</math><img src="./ff94658df45f78a364a59c7cc94eb37d5504db6d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.045ex; height:2.843ex;" alt="{\displaystyle 9n/10}" loading="lazy">, allowing the total time to be analyzed as a geometric series adding to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">. Unlike quickselect, this algorithm is deterministic, not randomized.<a href="#cite_note-clrs-2">[2]</a><a href="#cite_note-erickson-4">[4]</a><a href="#cite_note-bfprt-5">[5]</a> It was the first linear-time deterministic selection algorithm known,<a href="#cite_note-bfprt-5">[5]</a> and is commonly taught in undergraduate algorithms classes as an example of a <a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide and conquer</a> that does not divide into two equal subproblems.<a href="#cite_note-clrs-2">[2]</a><a href="#cite_note-erickson-4">[4]</a><a href="#cite_note-gootam-9">[9]</a><a href="#cite_note-gurwitz-16">[16]</a> However, the high constant factors in its <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> time bound make it slower than quickselect in practice,<a href="#cite_note-skiena-3">[3]</a><a href="#cite_note-gootam-9">[9]</a> and slower even than sorting for inputs of moderate size.<a href="#cite_note-erickson-4">[4]</a></li>

<li>Hybrid algorithms such as <a href="Introselect" title="Introselect">introselect</a> can be used to achieve the practical performance of quickselect with a fallback to medians of medians guaranteeing worst-case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> time.<a href="#cite_note-musser-17">[17]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Factories">Factories</h3></div>

The deterministic selection algorithms with the smallest known numbers of comparisons, for values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> that are far from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, are based on the concept of factories, introduced in 1976 by <a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Arnold Schönhage</a>, <a href="Mike_Paterson" title="Mike Paterson">Mike Paterson</a>, and <a href="Nick_Pippenger" title="Nick Pippenger">Nick Pippenger</a>.<a href="#cite_note-spp-18">[18]</a> These are methods that build <a href="Partial_order" class="mw-redirect" title="Partial order">partial orders</a> of certain specified types, on small subsets of input values, by using comparisons to combine smaller partial orders. As a very simple example, one type of factory can take as input a sequence of single-element partial orders, compare pairs of elements from these orders, and produce as output a sequence of two-element totally ordered sets. The elements used as the inputs to this factory could either be input values that have not been compared with anything yet, or "waste" values produced by other factories. The goal of a factory-based algorithm is to combine together different factories, with the outputs of some factories going to the inputs of others, in order to eventually obtain a partial order in which one element (the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest) is larger than some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k-1}</annotation>

</semantics>

</math><img src="./21363ebd7038c93aae93127e7d910fc1b2e2c745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}" loading="lazy"> other elements and smaller than another <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-k}</annotation>

</semantics>

</math><img src="./b98e1d6a69bccd09a4b9b69bdf03a08c1706c8c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.446ex; height:2.343ex;" alt="{\displaystyle n-k}" loading="lazy"> others. A careful design of these factories leads to an algorithm that, when applied to median-finding, uses at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2.942n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2.942n}</annotation>

</semantics>

</math><img src="./491f3baeb5fe9f96d053ddaea34244c1d463e792.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.691ex; height:2.176ex;" alt="{\displaystyle 2.942n}" loading="lazy"> comparisons. For other values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, the number of comparisons is smaller.<a href="#cite_note-dz99-19">[19]</a>

<div class="mw-heading mw-heading3"><h3 id="Parallel_algorithms">Parallel algorithms</h3></div>

<a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithms</a> for selection have been studied since 1975, when <a href="Leslie_Valiant" title="Leslie Valiant">Leslie Valiant</a> introduced the parallel comparison tree model for analyzing these algorithms, and proved that in this model selection using a linear number of comparisons requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\log \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (\log \log n)}</annotation>

</semantics>

</math><img src="./abd3ed358ca0ff406e846ab34eacde0685b93373.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.6ex; height:2.843ex;" alt="{\displaystyle \Omega (\log \log n)}" loading="lazy"> parallel steps, even for selecting the minimum or maximum.<a href="#cite_note-valiant-20">[20]</a> Researchers later found parallel algorithms for selection in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log n)}</annotation>

</semantics>

</math><img src="./a9f3ded7e013a35c8039ff3276bee6e183d7f1a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.695ex; height:2.843ex;" alt="{\displaystyle O(\log \log n)}" loading="lazy"> steps, matching this bound.<a href="#cite_note-akss-21">[21]</a><a href="#cite_note-azapip-22">[22]</a> In a randomized parallel comparison tree model it is possible to perform selection in a bounded number of steps and a linear number of comparisons.<a href="#cite_note-reischuk-23">[23]</a> On the more realistic <a href="Parallel_RAM" title="Parallel RAM">parallel RAM</a> model of computing, with exclusive read exclusive write memory access, selection can be performed in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n/\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n/\log n)}</annotation>

</semantics>

</math><img src="./1194637dca842caff484d434c24552c6e8baab44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.28ex; height:2.843ex;" alt="{\displaystyle O(n/\log n)}" loading="lazy"> processors, which is optimal both in time and in the number of processors.<a href="#cite_note-han-24">[24]</a> With concurrent memory access, slightly faster parallel time is possible in general,<a href="#cite_note-chr-25">[25]</a> and the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log n}</annotation>

</semantics>

</math><img src="./317ab5292da7c7935aec01a570461fe0613b21d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.754ex; height:2.509ex;" alt="{\displaystyle \log n}" loading="lazy"> term in the time bound can be replaced by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log k}</annotation>

</semantics>

</math><img src="./b6da5ed161853319a3a48f3c479cd0339bc5bded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.57ex; height:2.509ex;" alt="{\displaystyle \log k}" loading="lazy">.<a href="#cite_note-dieram-26">[26]</a>

<div class="mw-heading mw-heading3"><h3 id="Sublinear_data_structures">Sublinear data structures</h3></div>

When data is already organized into a <a href="Data_structure" title="Data structure">data structure</a>, it may be possible to perform selection in an amount of time that is sublinear in the number of values. As a simple case of this, for data already sorted into an array, selecting the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element may be performed by a single array lookup, in constant time.<a href="#cite_note-frejoh-27">[27]</a> For values organized into a two-dimensional array of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\times n}</annotation>

</semantics>

</math><img src="./12b23d207d23dd430b93320539abbb0bde84870d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.276ex; height:1.676ex;" alt="{\displaystyle m\times n}" loading="lazy">, with sorted rows and columns, selection may be performed in time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}</annotation>

</semantics>

</math><img src="./8bb9ff26cb355b4047486623acd4746151743a35.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:16.872ex; height:3.176ex;" alt="{\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}" loading="lazy">, or faster when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is small relative to the array dimensions.<a href="#cite_note-frejoh-27">[27]</a><a href="#cite_note-kkzz-28">[28]</a> For a collection of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> one-dimensional sorted arrays, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation>

</semantics>

</math><img src="./f29138ed3ad54ffce527daccadc49c520459b0b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}" loading="lazy"> items less than the selected item in the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">th array, the time is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}">

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}</annotation>

</semantics>

</math><img src="./d05afdcf41b80c23b8deca676d26ccc896f5317b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.32ex; height:3.176ex;" alt="{\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}" loading="lazy">.<a href="#cite_note-kkzz-28">[28]</a>

Selection from data in a <a href="Binary_heap" title="Binary heap">binary heap</a> takes time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(k)}</annotation>

</semantics>

</math><img src="./f5ec39041121b14e8c2b1a986c9b04547b223e3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.794ex; height:2.843ex;" alt="{\displaystyle O(k)}" loading="lazy">. This is independent of the size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> of the heap, and faster than the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(k\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(k\log n)}</annotation>

</semantics>

</math><img src="./5dcf3e2dc7b376b4d26d7574a5dced51ca5909df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.934ex; height:2.843ex;" alt="{\displaystyle O(k\log n)}" loading="lazy"> time bound that would be obtained from <a href="Best-first_search" title="Best-first search">best-first search</a>.<a href="#cite_note-kkzz-28">[28]</a><a href="#cite_note-frederickson-29">[29]</a> This same method can be applied more generally to data organized as any kind of heap-ordered tree (a tree in which each node stores one value in which the parent of each non-root node has a smaller value than its child). This method of performing selection in a heap has been applied to problems of listing multiple solutions to combinatorial optimization problems, such as finding the <a href="K_shortest_path_routing" title="K shortest path routing">k shortest paths</a> in a weighted graph, by defining a <a href="State_space_(computer_science)" title="State space (computer science)">state space</a> of solutions in the form of an <a href="Implicit_graph" title="Implicit graph">implicitly defined</a> heap-ordered tree, and then applying this selection algorithm to this tree.<a href="#cite_note-kpaths-30">[30]</a> In the other direction, linear time selection algorithms have been used as a subroutine in a <a href="Priority_queue" title="Priority queue">priority queue</a> data structure related to the heap, improving the time for extracting its <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th item from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log ^{*}n+\log k)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log ^{*}n+\log k)}</annotation>

</semantics>

</math><img src="./80d22d3661bc05e76d7f8ab567b23bb880c19f10.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.801ex; height:2.843ex;" alt="{\displaystyle O(\log ^{*}n+\log k)}" loading="lazy">; here <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log ^{*}n}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log ^{*}n}</annotation>

</semantics>

</math><img src="./566a9c5416bedcda38ab4993b73c3ea1b75c4ca9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log ^{*}n}" loading="lazy"> is the <a href="Iterated_logarithm" title="Iterated logarithm">iterated logarithm</a>.<a href="#cite_note-bks-31">[31]</a>

For a collection of data values undergoing dynamic insertions and deletions, the <a href="Order_statistic_tree" title="Order statistic tree">order statistic tree</a> augments a <a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">self-balancing binary search tree</a> structure with a constant amount of additional information per tree node, allowing insertions, deletions, and selection queries that ask for the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element in the current set to all be performed in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation>

</semantics>

</math><img src="./aae0f22048ba6b7c05dbae17b056bfa16e21807d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" loading="lazy"> time per operation.<a href="#cite_note-clrs-2">[2]</a> Going beyond the comparison model of computation, faster times per operation are possible for values that are small integers, on which binary arithmetic operations are allowed.<a href="#cite_note-pattho-32">[32]</a> It is not possible for a <a href="Streaming_algorithms" class="mw-redirect" title="Streaming algorithms">streaming algorithm</a> with memory sublinear in both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> to solve selection queries exactly for dynamic data, but the <a href="Count%E2%80%93min_sketch" title="Count–min sketch">count–min sketch</a> can be used to solve selection queries approximately, by finding a value whose position in the ordering of the elements (if it were added to them) would be within <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon n}</annotation>

</semantics>

</math><img src="./d08ac28ea9189a6aa89c1dc7e76c84c19e64e3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.478ex; height:1.676ex;" alt="{\displaystyle \varepsilon n}" loading="lazy"> steps of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, for a sketch whose size is within logarithmic factors of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/\varepsilon }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/\varepsilon }</annotation>

</semantics>

</math><img src="./c8a61384fb438a8f4019445c369caa1e9ae12e0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.408ex; height:2.843ex;" alt="{\displaystyle 1/\varepsilon }" loading="lazy">.<a href="#cite_note-cormut-33">[33]</a>

<div class="mw-heading mw-heading2"><h2 id="Lower_bounds">Lower bounds</h2></div>

The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> running time of the selection algorithms described above is necessary, because a selection algorithm that can handle inputs in an arbitrary order must take that much time to look at all of its inputs. If any one of its input values is not compared, that one value could be the one that should have been selected, and the algorithm can be made to produce an incorrect answer.<a href="#cite_note-kkzz-28">[28]</a> Beyond this simple argument, there has been a significant amount of research on the exact number of comparisons needed for selection, both in the randomized and deterministic cases.

Selecting the minimum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> values requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> comparisons, because the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> values that are not selected must each have been determined to be non-minimal, by being the largest in some comparison, and no two of these values can be largest in the same comparison. The same argument applies symmetrically to selecting the maximum.<a href="#cite_note-knuth-14">[14]</a>

The next simplest case is selecting the second-smallest. After several incorrect attempts, the first tight lower bound on this case was published in 1964 by Soviet mathematician <a href="Sergey_Kislitsyn" title="Sergey Kislitsyn">Sergey Kislitsyn</a>. It can be shown by observing that selecting the second-smallest also requires distinguishing the smallest value from the rest, and by considering the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> of comparisons involving the smallest value that an algorithm for this problem makes. Each of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> items that were compared to the smallest value is a candidate for second-smallest, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p-1}</annotation>

</semantics>

</math><img src="./f356ae51988add41a7da343e6b6d48fa968da162.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.262ex; height:2.509ex;" alt="{\displaystyle p-1}" loading="lazy"> of these values must be found larger than another value in a second comparison in order to rule them out as second-smallest.

With <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> values being the larger in at least one comparison, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p-1}</annotation>

</semantics>

</math><img src="./f356ae51988add41a7da343e6b6d48fa968da162.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.262ex; height:2.509ex;" alt="{\displaystyle p-1}" loading="lazy"> values being the larger in at least two comparisons, there are a total of at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+p-2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+p-2}</annotation>

</semantics>

</math><img src="./fc7ec22078067cd634b13ed4eabbf6b111ebbd81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.407ex; height:2.509ex;" alt="{\displaystyle n+p-2}" loading="lazy"> comparisons. An <a href="Adversary_model" title="Adversary model">adversary argument</a>, in which the outcome of each comparison is chosen in order to maximize <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> (subject to consistency with at least one possible ordering) rather than by the numerical values of the given items, shows that it is possible to force <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> to be at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}n}</annotation>

</semantics>

</math><img src="./d74677fc45e0d926639433586327cbc2982eae89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log _{2}n}" loading="lazy">. Therefore, the worst-case number of comparisons needed to select the second smallest is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+\lceil \log _{2}n\rceil -2}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+\lceil \log _{2}n\rceil -2}</annotation>

</semantics>

</math><img src="./e3795d577d447b01bc911a3931ca9b6a3c932ba9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.111ex; height:2.843ex;" alt="{\displaystyle n+\lceil \log _{2}n\rceil -2}" loading="lazy">, the same number that would be obtained by holding a single-elimination tournament with a run-off tournament among the values that lost to the smallest value. However, the expected number of comparisons of a randomized selection algorithm can be better than this bound; for instance, selecting the second-smallest of six elements requires seven comparisons in the worst case, but may be done by a randomized algorithm with an expected number of 6.5 comparisons.<a href="#cite_note-knuth-14">[14]</a>

More generally, selecting the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element out of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> requires at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+\min(k,n-k)-O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+\min(k,n-k)-O(1)}</annotation>

</semantics>

</math><img src="./c73d4a6ddf8aae90a24fcd8cb3abfb2d1c45cc7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.197ex; height:2.843ex;" alt="{\displaystyle n+\min(k,n-k)-O(1)}" loading="lazy"> comparisons, in the average case, matching the number of comparisons of the Floyd–Rivest algorithm up to its <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(n)}</annotation>

</semantics>

</math><img src="./afdac2125205278017cf549e9b004f8f6fd829c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.332ex; height:2.843ex;" alt="{\displaystyle o(n)}" loading="lazy"> term. The argument is made directly for deterministic algorithms, with a number of comparisons that is averaged over all possible <a href="Permutation" title="Permutation">permutations</a> of the input values.<a href="#cite_note-cunmun-1">[1]</a> By <a href="Yao's_principle" title="Yao's principle">Yao's principle</a>, it also applies to the expected number of comparisons for a randomized algorithm on its worst-case input.<a href="#cite_note-chan-34">[34]</a>

For deterministic algorithms, it has been shown that selecting the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th element requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}">

</mrow>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}</annotation>

</semantics>

</math><img src="./85e0db08ef65855ac63644f774d66f9647f080e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.827ex; height:3.176ex;" alt="{\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}" loading="lazy"> comparisons, where <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}</annotation>

</semantics>

</math> is the <a href="Binary_entropy_function" title="Binary entropy function">binary entropy function</a>.<a href="#cite_note-benjoh-35">[35]</a> The special case of median-finding has a slightly larger lower bound on the number of comparisons, at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2+\varepsilon )n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2+\varepsilon )n}</annotation>

</semantics>

</math><img src="./b183031b3d5f2f6819e9e8afb5ec1b445156047b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.29ex; height:2.843ex;" alt="{\displaystyle (2+\varepsilon )n}" loading="lazy">, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon \approx 2^{-80}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon \approx 2^{-80}}</annotation>

</semantics>

</math><img src="./e538a80355b2058ed17fa03975653221159e4637.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.499ex; height:2.676ex;" alt="{\displaystyle \varepsilon \approx 2^{-80}}" loading="lazy">.<a href="#cite_note-dz01-36">[36]</a>

<div class="mw-heading mw-heading2"><h2 id="Exact_numbers_of_comparisons">Exact numbers of comparisons</h2></div>

<a href="Donald_Knuth" title="Donald Knuth">Knuth</a> supplies the following triangle of numbers summarizing pairs of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> for which the exact number of comparisons needed by an optimal selection algorithm is known. The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">th row of the triangle (starting with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1}</annotation>

</semantics>

</math><img src="./d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" loading="lazy"> in the top row) gives the numbers of comparisons for inputs of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> values, and the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th number within each row gives the number of comparisons needed to select the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest value from an input of that size. The rows are symmetric because selecting the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest requires exactly the same number of comparisons, in the worst case, as selecting the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th largest.<a href="#cite_note-knuth-14">[14]</a>

Most, but not all, of the entries on the left half of each row can be found using the formula <math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}</annotation>

</semantics>

</math> This describes the number of comparisons made by a method of Abdollah Hadian and <a href="Milton_Sobel" title="Milton Sobel">Milton Sobel</a>, related to heapselect, that finds the smallest value using a single-elimination tournament and then repeatedly uses a smaller tournament among the values eliminated by the eventual tournament winners to find the next successive values until reaching the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">th smallest.<a href="#cite_note-knuth-14">[14]</a><a href="#cite_note-hadsob-37">[37]</a> Some of the larger entries were proven to be optimal using a computer search.<a href="#cite_note-knuth-14">[14]</a><a href="#cite_note-gkp-38">[38]</a>

<div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2></div>

Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is the <a href="Standard_Template_Library" title="Standard Template Library">Standard Template Library</a> for <a href="C%2B%2B" title="C++">C++</a>, which provides a templated <code>nth_element</code> method with a guarantee of expected linear time.<a href="#cite_note-skiena-3">[3]</a>

<a href="Python_(programming_language)" title="Python (programming language)">Python</a>'s standard library includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a <a href="Binary_heap" title="Binary heap">binary heap</a>, limited to holding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> elements, and initialized to the first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O((n-k)+k\log k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O((n-k)+k\log k)}</annotation>

</semantics>

</math><img src="./a9852911449ce4b6ca97f2c4893f9ede7cdda7c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.847ex; height:2.843ex;" alt="{\displaystyle O((n-k)+k\log k)}" loading="lazy"> for already sorted data. The worst-case is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log k)}</annotation>

</semantics>

</math><img src="./99e71cfbbb1dbd170050e63d7b342b07b4b014e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.934ex; height:2.843ex;" alt="{\displaystyle O(n\log k)}" loading="lazy"> for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.<a href="#cite_note-python-39">[39]</a>

Since 2017, <a href="Matlab" class="mw-redirect" title="Matlab">Matlab</a> has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running time is.<a href="#cite_note-matlab-40">[40]</a>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<a href="Quickselect" title="Quickselect">Quickselect</a> was presented without analysis by <a href="Tony_Hoare" title="Tony Hoare">Tony Hoare</a> in 1965,<a href="#cite_note-hoare-41">[41]</a> and first analyzed in a 1971 technical report by <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>.<a href="#cite_note-floriv-11">[11]</a> The first known linear time deterministic selection algorithm is the <a href="Median_of_medians" title="Median of medians">median of medians</a> method, published in 1973 by <a href="Manuel_Blum" title="Manuel Blum">Manuel Blum</a>, <a href="Robert_W._Floyd" title="Robert W. Floyd">Robert W. Floyd</a>, <a href="Vaughan_Pratt" title="Vaughan Pratt">Vaughan Pratt</a>, <a href="Ron_Rivest" title="Ron Rivest">Ron Rivest</a>, and <a href="Robert_Tarjan" title="Robert Tarjan">Robert Tarjan</a>.<a href="#cite_note-bfprt-5">[5]</a> They trace the formulation of the selection problem to work of Charles L. Dodgson (better known as <a href="Lewis_Carroll" title="Lewis Carroll">Lewis Carroll</a>) who in 1883 pointed out that the usual design of single-elimination sports tournaments does not guarantee that the second-best player wins second place,<a href="#cite_note-bfprt-5">[5]</a><a href="#cite_note-carroll-42">[42]</a> and to work of <a href="Hugo_Steinhaus" title="Hugo Steinhaus">Hugo Steinhaus</a> circa 1930, who followed up this same line of thought by asking for a tournament design that can make this guarantee, with a minimum number of games played (that is, comparisons).<a href="#cite_note-bfprt-5">[5]</a>

<ul><li><a href="Geometric_median#Computation" title="Geometric median">Geometric median § Computation</a>, algorithms for higher-dimensional generalizations of medians</li>

<li><a href="Median_filter" title="Median filter">Median filter</a>, application of median-finding algorithms in image processing</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCuntoMunro1989" class="citation journal cs1">Cunto, Walter; <a href="Ian_Munro_(computer_scientist)" title="Ian Munro (computer scientist)">Munro, J. Ian</a> (1989). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62044.62047">"Average case selection"</a>. <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>. 36 (2): 270–279. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F62044.62047">10.1145/62044.62047</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1072421">1072421</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10947879">10947879</a>.</cite>

</li>

<li id="cite_note-clrs-2">^ <a href="#cite_ref-clrs_2-0">a</a> <a href="#cite_ref-clrs_2-1">b</a> <a href="#cite_ref-clrs_2-2">c</a> <a href="#cite_ref-clrs_2-3">d</a> <a href="#cite_ref-clrs_2-4">e</a> <a href="#cite_ref-clrs_2-5">f</a> <a href="#cite_ref-clrs_2-6">g</a> <a href="#cite_ref-clrs_2-7">h</a> <cite id="CITEREFCormenLeisersonRivestStein2009" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2009) [1990]. "Chapter 9: Medians and order statistics". <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a> (3rd ed.). MIT Press and McGraw-Hill. pp. 213–227. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03384-4</bdi>.</cite>; "Section 14.1: Dynamic order statistics", pp. 339–345

</li>

<li id="cite_note-skiena-3">^ <a href="#cite_ref-skiena_3-0">a</a> <a href="#cite_ref-skiena_3-1">b</a> <a href="#cite_ref-skiena_3-2">c</a> <a href="#cite_ref-skiena_3-3">d</a> <cite id="CITEREFSkiena2020" class="citation book cs1"><a href="Steven_Skiena" title="Steven Skiena">Skiena, Steven S.</a> (2020). "17.3: Median and selection". The Algorithm Design Manual. Texts in Computer Science (Third ed.). Springer. pp. 514–516. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-54256-6">10.1007/978-3-030-54256-6</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-54255-9</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=4241430">4241430</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:22382667">22382667</a>.</cite>

</li>

<li id="cite_note-erickson-4">^ <a href="#cite_ref-erickson_4-0">a</a> <a href="#cite_ref-erickson_4-1">b</a> <a href="#cite_ref-erickson_4-2">c</a> <a href="#cite_ref-erickson_4-3">d</a> <a href="#cite_ref-erickson_4-4">e</a> <cite id="CITEREFErickson2019" class="citation book cs1">Erickson, Jeff (June 2019). "1.8: Linear-time selection". <a rel="nofollow" class="external text" href="https://jeffe.cs.illinois.edu/teaching/algorithms/">Algorithms</a>. pp. 35–39.</cite>

</li>

<li id="cite_note-bfprt-5">^ <a href="#cite_ref-bfprt_5-0">a</a> <a href="#cite_ref-bfprt_5-1">b</a> <a href="#cite_ref-bfprt_5-2">c</a> <a href="#cite_ref-bfprt_5-3">d</a> <a href="#cite_ref-bfprt_5-4">e</a> <a href="#cite_ref-bfprt_5-5">f</a> <cite id="CITEREFBlumFloydPrattRivest1973" class="citation journal cs1"><a href="Manuel_Blum" title="Manuel Blum">Blum, Manuel</a>; <a href="Robert_W._Floyd" title="Robert W. Floyd">Floyd, Robert W.</a>; <a href="Vaughan_Pratt" title="Vaughan Pratt">Pratt, Vaughan</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1973). <a rel="nofollow" class="external text" href="http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf">"Time bounds for selection"</a> (PDF). <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>. 7 (4): 448–461. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2873%2980033-9">10.1016/S0022-0000(73)80033-9</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0329916">0329916</a>.</cite>

</li>

<li id="cite_note-brodal-6"><a href="#cite_ref-brodal_6-0">^</a> <cite id="CITEREFBrodal2013" class="citation conference cs1"><a href="Gerth_St%C3%B8lting_Brodal" class="mw-redirect" title="Gerth Stølting Brodal">Brodal, Gerth Stølting</a> (2013). "A survey on priority queues". In Brodnik, Andrej; López-Ortiz, Alejandro; Raman, Venkatesh; Viola, Alfredo (eds.). Space-Efficient Data Structures, Streams, and Algorithms – Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Lecture Notes in Computer Science. Vol. 8066. Springer. pp. 150–163. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-40273-9_11">10.1007/978-3-642-40273-9_11</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-40272-2</bdi>.</cite>

</li>

<li id="cite_note-kletar-7">^ <a href="#cite_ref-kletar_7-0">a</a> <a href="#cite_ref-kletar_7-1">b</a> <a href="#cite_ref-kletar_7-2">c</a> <a href="#cite_ref-kletar_7-3">d</a> <cite id="CITEREFKleinbergTardos2006" class="citation book cs1"><a href="Jon_Kleinberg" title="Jon Kleinberg">Kleinberg, Jon</a>; <a href="%C3%89va_Tardos" title="Éva Tardos">Tardos, Éva</a> (2006). "13.5 Randomized divide and conquer: median-finding and quicksort". Algorithm Design. Addison-Wesley. pp. 727–734. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780321295354</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> For instance, Cormen et al. use an in-place array partition, while Kleinberg and Tardos describe the input as a set and use a method that partitions it into two new sets.

</li>

<li id="cite_note-gootam-9">^ <a href="#cite_ref-gootam_9-0">a</a> <a href="#cite_ref-gootam_9-1">b</a> <a href="#cite_ref-gootam_9-2">c</a> <a href="#cite_ref-gootam_9-3">d</a> <cite id="CITEREFGoodrichTamassia2015" class="citation book cs1"><a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; <a href="Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a> (2015). "9.2: Selection". Algorithm Design and Applications. Wiley. pp. 270–275. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-118-33591-8</bdi>.</cite>

</li>

<li id="cite_note-devroye-10"><a href="#cite_ref-devroye_10-0">^</a> <cite id="CITEREFDevroye1984" class="citation journal cs1">Devroye, Luc (1984). <a rel="nofollow" class="external text" href="http://luc.devroye.org/devroye-selection1984.pdf">"Exponential bounds for the running time of a selection algorithm"</a> (PDF). Journal of Computer and System Sciences. 29 (1): 1–7. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2884%2990009-6">10.1016/0022-0000(84)90009-6</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0761047">0761047</a>.</cite> <cite id="CITEREFDevroye2001" class="citation journal cs1">Devroye, Luc (2001). <a rel="nofollow" class="external text" href="https://luc.devroye.org/wcfind.pdf">"On the probabilistic worst-case time of 'find'"</a> (PDF). Algorithmica. 31 (3): 291–303. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-001-0046-2">10.1007/s00453-001-0046-2</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1855252">1855252</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:674040">674040</a>.</cite>

</li>

<li id="cite_note-floriv-11">^ <a href="#cite_ref-floriv_11-0">a</a> <a href="#cite_ref-floriv_11-1">b</a> <cite id="CITEREFFloydRivest1975" class="citation journal cs1"><a href="Robert_W._Floyd" title="Robert W. Floyd">Floyd, Robert W.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a> (March 1975). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F360680.360691">"Expected time bounds for selection"</a>. <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>. 18 (3): 165–172. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F360680.360691">10.1145/360680.360691</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3064709">3064709</a>.</cite> See also "Algorithm 489: the algorithm SELECT—for finding the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">th smallest of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements", p. 173, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F360680.360694">10.1145/360680.360694</a>.

</li>

<li id="cite_note-brown-12"><a href="#cite_ref-brown_12-0">^</a> <cite id="CITEREFBrown1976" class="citation journal cs1">Brown, Theodore (September 1976). "Remark on Algorithm 489". ACM Transactions on Mathematical Software. 2 (3): 301–304. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F355694.355704">10.1145/355694.355704</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13985011">13985011</a>.</cite>

</li>

<li id="cite_note-prt-13"><a href="#cite_ref-prt_13-0">^</a> <cite id="CITEREFPostmusRinnooy_KanTimmer1983" class="citation journal cs1">Postmus, J. T.; <a href="Alexander_Rinnooy_Kan" title="Alexander Rinnooy Kan">Rinnooy Kan, A. H. G.</a>; Timmer, G. T. (1983). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F182.358440">"An efficient dynamic selection method"</a>. <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>. 26 (11): 878–881. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F182.358440">10.1145/182.358440</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0784120">0784120</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3211474">3211474</a>.</cite>

</li>

<li id="cite_note-knuth-14">^ <a href="#cite_ref-knuth_14-0">a</a> <a href="#cite_ref-knuth_14-1">b</a> <a href="#cite_ref-knuth_14-2">c</a> <a href="#cite_ref-knuth_14-3">d</a> <a href="#cite_ref-knuth_14-4">e</a> <a href="#cite_ref-knuth_14-5">f</a> <cite id="CITEREFKnuth1998" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1998). "Section 5.3.3: Minimum-comparison selection". <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming, Volume 3: Sorting and Searching</a> (2nd ed.). Addison-Wesley. pp. 207–219. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89685-0</bdi>.</cite>

</li>

<li id="cite_note-karrag-15"><a href="#cite_ref-karrag_15-0">^</a> <cite id="CITEREFKarloffRaghavan1993" class="citation journal cs1">Karloff, Howard J.; <a href="Prabhakar_Raghavan" title="Prabhakar Raghavan">Raghavan, Prabhakar</a> (1993). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F174130.174132">"Randomized algorithms and pseudorandom numbers"</a>. <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>. 40 (3): 454–476. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F174130.174132">10.1145/174130.174132</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1370358">1370358</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17956460">17956460</a>.</cite>

</li>

<li id="cite_note-gurwitz-16"><a href="#cite_ref-gurwitz_16-0">^</a> <cite id="CITEREFGurwitz1992" class="citation journal cs1">Gurwitz, Chaya (1992). "On teaching median-finding algorithms". IEEE Transactions on Education. 35 (3): 230–232. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1992ITEdu..35..230G">1992ITEdu..35..230G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F13.144650">10.1109/13.144650</a>.</cite>

</li>

<li id="cite_note-musser-17"><a href="#cite_ref-musser_17-0">^</a> <cite id="CITEREFMusser1997" class="citation journal cs1">Musser, David R. (August 1997). "Introspective sorting and selection algorithms". Software: Practice and Experience. 27 (8). Wiley: 983–993. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2F%28sici%291097-024x%28199708%2927%3A8%3C983%3A%3Aaid-spe117%3E3.0.co%3B2-%23">10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-#</a>.</cite>

</li>

<li id="cite_note-spp-18"><a href="#cite_ref-spp_18-0">^</a> <cite id="CITEREFSchönhagePatersonPippenger1976" class="citation journal cs1"><a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Schönhage, A.</a>; <a href="Mike_Paterson" title="Mike Paterson">Paterson, M.</a>; <a href="Nick_Pippenger" title="Nick Pippenger">Pippenger, N.</a> (1976). "Finding the median". <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>. 13 (2): 184–199. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2876%2980029-3">10.1016/S0022-0000(76)80029-3</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0428794">0428794</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29867292">29867292</a>.</cite>

</li>

<li id="cite_note-dz99-19"><a href="#cite_ref-dz99_19-0">^</a> <cite id="CITEREFDorZwick1999" class="citation journal cs1"><a href="Dorit_Dor" title="Dorit Dor">Dor, Dorit</a>; <a href="Uri_Zwick" title="Uri Zwick">Zwick, Uri</a> (1999). "Selecting the median". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 28 (5): 1722–1758. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539795288611">10.1137/S0097539795288611</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1694164">1694164</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2633282">2633282</a>.</cite>

</li>

<li id="cite_note-valiant-20"><a href="#cite_ref-valiant_20-0">^</a> <cite id="CITEREFValiant1975" class="citation journal cs1"><a href="Leslie_Valiant" title="Leslie Valiant">Valiant, Leslie G.</a> (1975). "Parallelism in comparison problems". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 4 (3): 348–355. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0204030">10.1137/0204030</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0378467">0378467</a>.</cite>

</li>

<li id="cite_note-akss-21"><a href="#cite_ref-akss_21-0">^</a> <cite id="CITEREFAjtaiKomlósSteigerSzemerédi1989" class="citation journal cs1"><a href="Mikl%C3%B3s_Ajtai" title="Miklós Ajtai">Ajtai, Miklós</a>; <a href="J%C3%A1nos_Koml%C3%B3s_(mathematician)" title="János Komlós (mathematician)">Komlós, János</a>; Steiger, W. L.; <a href="Endre_Szemer%C3%A9di" title="Endre Szemerédi">Szemerédi, Endre</a> (1989). "Optimal parallel selection has complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log \log n)}</annotation>

</semantics>

</math><img src="./a9f3ded7e013a35c8039ff3276bee6e183d7f1a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.695ex; height:2.843ex;" alt="{\displaystyle O(\log \log n)}" loading="lazy">". <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>. 38 (1): 125–133. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2889%2990035-4">10.1016/0022-0000(89)90035-4</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0990052">0990052</a>.</cite>

</li>

<li id="cite_note-azapip-22"><a href="#cite_ref-azapip_22-0">^</a> <cite id="CITEREFAzarPippenger1990" class="citation journal cs1">Azar, Yossi; <a href="Nick_Pippenger" title="Nick Pippenger">Pippenger, Nicholas</a> (1990). "Parallel selection". <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>. 27 (1–2): 49–58. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0166-218X%2890%2990128-Y">10.1016/0166-218X(90)90128-Y</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1055590">1055590</a>.</cite>

</li>

<li id="cite_note-reischuk-23"><a href="#cite_ref-reischuk_23-0">^</a> <cite id="CITEREFReischuk1985" class="citation journal cs1">Reischuk, Rüdiger (1985). "Probabilistic parallel algorithms for sorting and selection". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 14 (2): 396–409. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0214030">10.1137/0214030</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0784745">0784745</a>.</cite>

</li>

<li id="cite_note-han-24"><a href="#cite_ref-han_24-0">^</a> <cite id="CITEREFHan2007" class="citation journal cs1">Han, Yijie (2007). "Optimal parallel selection". <a href="ACM_Transactions_on_Algorithms" title="ACM Transactions on Algorithms">ACM Transactions on Algorithms</a>. 3 (4): A38:1–A38:11. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1290672.1290675">10.1145/1290672.1290675</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2364962">2364962</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9645870">9645870</a>.</cite>

</li>

<li id="cite_note-chr-25"><a href="#cite_ref-chr_25-0">^</a> <cite id="CITEREFChaudhuriHagerupRaman1993" class="citation conference cs1">Chaudhuri, Shiva; Hagerup, Torben; Raman, Rajeev (1993). "Approximate and exact deterministic parallel selection". In Borzyszkowski, Andrzej M.; Sokolowski, Stefan (eds.). Mathematical Foundations of Computer Science 1993, 18th International Symposium, MFCS'93, Gdansk, Poland, August 30 – September 3, 1993, Proceedings. Lecture Notes in Computer Science. Vol. 711. Springer. pp. 352–361. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-57182-5_27">10.1007/3-540-57182-5_27</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/11858%2F00-001M-0000-0014-B748-C">11858/00-001M-0000-0014-B748-C</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-57182-7</bdi>.</cite>

</li>

<li id="cite_note-dieram-26"><a href="#cite_ref-dieram_26-0">^</a> <cite id="CITEREFDietzRaman1999" class="citation journal cs1">Dietz, Paul F.; Raman, Rajeev (1999). "Small-rank selection in parallel, with applications to heap construction". <a href="Journal_of_Algorithms" class="mw-redirect" title="Journal of Algorithms">Journal of Algorithms</a>. 30 (1): 33–51. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjagm.1998.0971">10.1006/jagm.1998.0971</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1661179">1661179</a>.</cite>

</li>

<li id="cite_note-frejoh-27">^ <a href="#cite_ref-frejoh_27-0">a</a> <a href="#cite_ref-frejoh_27-1">b</a> <cite id="CITEREFFredericksonJohnson1984" class="citation journal cs1">Frederickson, Greg N.; <a href="Donald_B._Johnson" title="Donald B. Johnson">Johnson, Donald B.</a> (1984). "Generalized selection and ranking: sorted matrices". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 13 (1): 14–30. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0213002">10.1137/0213002</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0731024">0731024</a>.</cite>

</li>

<li id="cite_note-kkzz-28">^ <a href="#cite_ref-kkzz_28-0">a</a> <a href="#cite_ref-kkzz_28-1">b</a> <a href="#cite_ref-kkzz_28-2">c</a> <a href="#cite_ref-kkzz_28-3">d</a> <cite id="CITEREFKaplanKozmaZamirZwick2019" class="citation conference cs1">Kaplan, Haim; Kozma, László; Zamir, Or; <a href="Uri_Zwick" title="Uri Zwick">Zwick, Uri</a> (2019). "Selection from heaps, row-sorted matrices, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X+Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X+Y}</annotation>

</semantics>

</math><img src="./191744cf9cddeff3ab2e750e22bcfce7766d355e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.594ex; height:2.343ex;" alt="{\displaystyle X+Y}" loading="lazy"> using soft heaps". In Fineman, Jeremy T.; <a href="Michael_Mitzenmacher" title="Michael Mitzenmacher">Mitzenmacher, Michael</a> (eds.). 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA. OASIcs. Vol. 69. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 5:1–5:21. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1802.07041">1802.07041</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FOASIcs.SOSA.2019.5">10.4230/OASIcs.SOSA.2019.5</a>.</cite>

</li>

<li id="cite_note-frederickson-29"><a href="#cite_ref-frederickson_29-0">^</a> <cite id="CITEREFFrederickson1993" class="citation journal cs1">Frederickson, Greg N. (1993). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.1993.1030">"An optimal algorithm for selection in a min-heap"</a>. <a href="Information_and_Computation" title="Information and Computation">Information and Computation</a>. 104 (2): 197–214. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.1993.1030">10.1006/inco.1993.1030</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1221889">1221889</a>.</cite>

</li>

<li id="cite_note-kpaths-30"><a href="#cite_ref-kpaths_30-0">^</a> <cite id="CITEREFEppstein1999" class="citation journal cs1"><a href="David_Eppstein" title="David Eppstein">Eppstein, David</a> (1999). "Finding the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> shortest paths". <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 28 (2): 652–673. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539795290477">10.1137/S0097539795290477</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1634364">1634364</a>.</cite>

</li>

<li id="cite_note-bks-31"><a href="#cite_ref-bks_31-0">^</a> <cite id="CITEREFBabenkoKolesnichenkoSmirnov2019" class="citation journal cs1">Babenko, Maxim; Kolesnichenko, Ignat; Smirnov, Ivan (2019). "Cascade heap: towards time-optimal extractions". Theory of Computing Systems. 63 (4): 637–646. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00224-018-9866-1">10.1007/s00224-018-9866-1</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3942251">3942251</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:253740380">253740380</a>.</cite>

</li>

<li id="cite_note-pattho-32"><a href="#cite_ref-pattho_32-0">^</a> <cite id="CITEREFPătraşcuThorup2014" class="citation conference cs1"><a href="Mihai_P%C4%83tra%C8%99cu_(computer_scientist)" title="Mihai Pătrașcu (computer scientist)">Pătraşcu, Mihai</a>; Thorup, Mikkel (2014). "Dynamic integer sets with optimal rank, select, and predecessor search". 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014. IEEE Computer Society. pp. 166–175. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1408.3045">1408.3045</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS.2014.26">10.1109/FOCS.2014.26</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4799-6517-5</bdi>.</cite>

</li>

<li id="cite_note-cormut-33"><a href="#cite_ref-cormut_33-0">^</a> <cite id="CITEREFCormodeMuthukrishnan2005" class="citation journal cs1">Cormode, Graham; <a href="S._Muthukrishnan_(computer_scientist)" title="S. Muthukrishnan (computer scientist)">Muthukrishnan, S.</a> (2005). "An improved data stream summary: the count-min sketch and its applications". Journal of Algorithms. 55 (1): 58–75. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jalgor.2003.12.001">10.1016/j.jalgor.2003.12.001</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2132028">2132028</a>.</cite>

</li>

<li id="cite_note-chan-34"><a href="#cite_ref-chan_34-0">^</a> <cite id="CITEREFChan2010" class="citation journal cs1"><a href="Timothy_M._Chan" title="Timothy M. Chan">Chan, Timothy M.</a> (2010). "Comparison-based time-space lower bounds for selection". <a href="ACM_Transactions_on_Algorithms" title="ACM Transactions on Algorithms">ACM Transactions on Algorithms</a>. 6 (2): A26:1–A26:16. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1721837.1721842">10.1145/1721837.1721842</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2675693">2675693</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11742607">11742607</a>.</cite>

</li>

<li id="cite_note-benjoh-35"><a href="#cite_ref-benjoh_35-0">^</a> <cite id="CITEREFBentJohn1985" class="citation conference cs1">Bent, Samuel W.; John, John W. (1985). "Finding the median requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n}</annotation>

</semantics>

</math><img src="./134afa8ff09fdddd24b06f289e92e3a045092bd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.557ex; height:2.176ex;" alt="{\displaystyle 2n}" loading="lazy"> comparisons". In Sedgewick, Robert (ed.). Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6–8, 1985, Providence, Rhode Island, USA. Association for Computing Machinery. pp. 213–216. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F22145.22169">10.1145/22145.22169</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-151-2</bdi>.</cite>

</li>

<li id="cite_note-dz01-36"><a href="#cite_ref-dz01_36-0">^</a> <cite id="CITEREFDorZwick2001" class="citation journal cs1"><a href="Dorit_Dor" title="Dorit Dor">Dor, Dorit</a>; <a href="Uri_Zwick" title="Uri Zwick">Zwick, Uri</a> (2001). "Median selection requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (2+\varepsilon )N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (2+\varepsilon )N}</annotation>

</semantics>

</math><img src="./67fabbc214266cef17c8695750aaaaef59be5a91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.959ex; height:2.843ex;" alt="{\displaystyle (2+\varepsilon )N}" loading="lazy"> comparisons". <a href="SIAM_Journal_on_Discrete_Mathematics" title="SIAM Journal on Discrete Mathematics">SIAM Journal on Discrete Mathematics</a>. 14 (3): 312–325. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0895480199353895">10.1137/S0895480199353895</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1857348">1857348</a>.</cite>

</li>

<li id="cite_note-hadsob-37"><a href="#cite_ref-hadsob_37-0">^</a> <cite id="CITEREFHadianSobel1969" class="citation report cs1">Hadian, Abdollah; <a href="Milton_Sobel" title="Milton Sobel">Sobel, Milton</a> (May 1969). Selecting the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">-th largest using binary errorless comparisons (Report). School of Statistics Technical Reports. Vol. 121. University of Minnesota. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/11299%2F199105">11299/199105</a>.</cite>

</li>

<li id="cite_note-gkp-38"><a href="#cite_ref-gkp_38-0">^</a> <cite id="CITEREFGasarchKellyPugh1996" class="citation journal cs1"><a href="William_Gasarch" title="William Gasarch">Gasarch, William</a>; Kelly, Wayne; Pugh, William (July 1996). "Finding the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">th largest of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> for small <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i,n}</annotation>

</semantics>

</math><img src="./965d4692e2b57722d70b0c61c696208ef6295d0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.231ex; height:2.509ex;" alt="{\displaystyle i,n}" loading="lazy">". <a href="ACM_SIGACT_News" class="mw-redirect" title="ACM SIGACT News">ACM SIGACT News</a>. 27 (2): 88–96. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F235767.235772">10.1145/235767.235772</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3133332">3133332</a>.</cite>

</li>

<li id="cite_note-python-39"><a href="#cite_ref-python_39-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/python/cpython/blob/main/Lib/heapq.py">"heapq package source code"</a>. Python library. Retrieved 2023-08-06.</cite>; see also the linked <a rel="nofollow" class="external text" href="https://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/">comparison of algorithm performance on best-case data</a>.

</li>

<li id="cite_note-matlab-40"><a href="#cite_ref-matlab_40-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.mathworks.com/help/matlab/ref/mink.html">"mink: Find k smallest elements of array"</a>. Matlab R2023a documentation. Mathworks. Retrieved 2023-03-30.</cite>

</li>

<li id="cite_note-hoare-41"><a href="#cite_ref-hoare_41-0">^</a> <cite id="CITEREFHoare1961" class="citation journal cs1"><a href="Tony_Hoare" title="Tony Hoare">Hoare, C. A. R.</a> (July 1961). "Algorithm 65: Find". <a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a>. 4 (7): 321–322. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F366622.366647">10.1145/366622.366647</a>.</cite>

</li>

<li id="cite_note-carroll-42"><a href="#cite_ref-carroll_42-0">^</a> <cite id="CITEREFDodgson1883" class="citation book cs1"><a href="Lewis_Carroll" title="Lewis Carroll">Dodgson, Charles L.</a> (1883). Lawn Tennis Tournaments: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Method. London: Macmillan and Co.</cite> See also <cite id="CITEREFWilsonMoktefi2019" class="citation book cs1">Wilson, Robin; Moktefi, Amirouche, eds. (2019). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=OBGIDwAAQBAJ&pg=PA129">"Lawn tennis tournaments"</a>. The Mathematical World of Charles L. Dodgson (Lewis Carroll). Oxford University Press. p. 129. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780192549013</bdi>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-28" href="https://en.wikipedia.org/wiki/?title=Selection_algorithm&oldid=1272480370">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>